package l.l.w.Offer.ReConstructBinaryTree;

import java.util.Arrays;

/**
 * Created by llw on 2017/9/8.
 */
public class ReConstructBinaryTree {

    public TreeNode reConstructBinaryTreeByPreAndInOrder(int [] pre, int [] in){
        if(pre == null) return null;
        if(pre.length != in.length) return null;
        if(pre.length == 0) return  null;
        return reConstructBinaryTreeByPreAndInOrder(pre,0,pre.length-1,in,0,pre.length-1);
    }
    /**
     * 递归构造二叉树
     * @param pre   前序遍历的结果
     * @param preStart start与end决定了处理哪些节点
     * @param preEnd
     * @param in    后序遍历的结果
     * @param inStart
     * @param inEnd
     * @return
     */
    private TreeNode reConstructBinaryTreeByPreAndInOrder(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        if(preStart > preEnd) return null;
        TreeNode node = new TreeNode(pre[preStart]);
        int index = find(in,pre[preStart]); //找到根在中序遍历的结果的位置
        //然后得到左子树和右子树对应的部分，分别递归的处理左子树和右子树
        node.left = reConstructBinaryTreeByPreAndInOrder(pre,preStart+1,preStart+index-inStart,in,inStart,index-1);
        node.right = reConstructBinaryTreeByPreAndInOrder(pre,preStart+index-inStart+1,preEnd,in,index+1,inEnd);
        return node;
    }
    private static int find(int[] in, int num) {
//        assert i 属于in
        for(int j=0;j<in.length;++j){
            if(in[j]==num)
                return j;
        }
        return 0;
    }

    /**
     * 根据后序和中序重建二叉树
     * @param post
     * @param in
     * @return
     */
    public static TreeNode reConstructBinaryTreeByPostAndInOrder(int[] post,int[] in){
        if(post == null) return null;
        if(post.length != in.length) return null;
        if(post.length == 0) return  null;
        return reConstructBinaryTreeByPostAndInOrder(post,0,post.length-1,in,0,in.length-1);
    }
    private static TreeNode reConstructBinaryTreeByPostAndInOrder(int[] post, int postStart, int postEnd, int[] in, int inStart, int inEnd) {
        if(postStart > postEnd) return  null;//不会出现的。。。
        // 因为进来的时候要么【postStart，postStart+index-inStart】
        //要么是【postStart+index-inStart+1，postEnd-1】
        //并且中序的start和end也很重要，不能有错！！！
        TreeNode node = new TreeNode(post[postEnd]);
        if(postStart == postEnd)
            return  node;
        int index = find(in, post[postEnd]);
        node.left = reConstructBinaryTreeByPostAndInOrder(post,postStart,postStart+index-inStart-1,in,inStart,index-1);
        node.right = reConstructBinaryTreeByPostAndInOrder(post,postStart+index-inStart,postEnd-1,in,index+1,inEnd);
        return node;
    }

    /**
     * 通过前序和中序，不构造二叉树直接输出后序遍历
     * @param pre
     * @param in
     * @return
     */
    public static int[] getPostOrderAccordingInAndPreOrder(int[] pre, int[] in){
        int[] post = new int[pre.length];
        getPostOrderAccordingInAndPreOrder(pre,0,pre.length-1,in,0,in.length-1,post,pre.length-1);
        return post;
    }

    private static int getPostOrderAccordingInAndPreOrder(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd, int[] post, int i) {
        if(preStart > preEnd) return i;
        post[i--] = pre[preStart];
        int index = find(in, pre[preStart]);
        i = getPostOrderAccordingInAndPreOrder(pre,preStart+index-inStart+1,preEnd,in,index+1,inEnd,post,i);
        i = getPostOrderAccordingInAndPreOrder(pre,preStart+1,preStart+index - inStart,in,inStart,index-1,post,i);
        return i;
    }

    /**
     * 根据中序和后序，不构造二叉树，直接输出前序遍历
     * @param in
     * @param post
     * @return
     */
    public static int[] getPreOrderAccordingInAndPostOrder(int[] in, int[] post){
        int[] pre = new int[in.length];
        getPreOrderAccordingInAndPostOrder(post,0,post.length-1,in,0,in.length-1,pre,0);
        return pre;
    }

    private static int getPreOrderAccordingInAndPostOrder(int[] post, int postStart, int postEnd, int[] in, int inStart, int inEnd, int[] pre, int i) {
        if(postStart > postEnd) return i;
        pre[i++] = post[postEnd];
        if(postStart == postEnd) return i;
        int index = find(in, post[postEnd]);
        i = getPreOrderAccordingInAndPostOrder(post,postStart,postStart+index-inStart-1,in,inStart,index-1,pre,i);
        i=getPreOrderAccordingInAndPostOrder(post,postStart+index-inStart,postEnd-1,in,index+1,inEnd,pre,i);
        return i;
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        int[] post = {7,4,2,5,8,6,3,1};
        TreeNode treeNode = new ReConstructBinaryTree().reConstructBinaryTreeByPreAndInOrder(pre, in);
        System.out.println(treeNode);

        TreeNode root2 = reConstructBinaryTreeByPostAndInOrder(post, in);
        System.out.println(root2);

        int[] getPost = getPostOrderAccordingInAndPreOrder(pre, in);
        System.out.println(Arrays.toString(getPost));

        int[] getPre = getPreOrderAccordingInAndPostOrder(in,post);
        System.out.println(Arrays.toString(getPre));
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
